﻿using System;
using System.Collections.Generic;
using System.Linq;
using Algoritmia.DataStructures.Digraphs;
using Algoritmia.DataStructures.MergeFindSets;

namespace Algoritmia.Problems.ConnectedComponents
{
    public class SetMergingConnectedComponentsFinder<T> : IConnectedComponentsFinder<T>
        where T : IEquatable<T>
    {
        private readonly Func<IEnumerable<T>, IMergeFindSet<T>> _createMFSet;

        public SetMergingConnectedComponentsFinder(Func<IEnumerable<T>,IMergeFindSet<T>> createMFSet = null)
        {
            _createMFSet = createMFSet ?? ( it => new MergeFindSet<T>(from e in it 
                                                                      select new[] {e})) ;
        }

        #region IConnectedComponentsFinder<T> Members

        public IEnumerable<IEnumerable<T>> ConnectedComponents(IDigraph<T> g)
        {
            var mfSet = _createMFSet(g.V);
            foreach(var edge in g.E)
            {
                mfSet.Merge(edge.Item1,edge.Item2);
            }
            return mfSet;
        }

        #endregion
    }
}
